package leetcode.editor.cn.util.tree.bstree;

public class BinarySearchTree {
    public TreeNode root;
    protected int size;

    protected TreeNode createNode(int value, TreeNode parent, TreeNode left, TreeNode right) {
        return new TreeNode(value, parent, left, right);
    }

    public TreeNode search(int element) {
        TreeNode node = root;
        while (node != null && node.val != null && node.val != element) {
            if (element < node.val) {
                node = node.left;
            } else {
                node = node.right;
            }
        }

        return node;
    }

    public TreeNode insert(int element) {
        if (root == null) {
            root = createNode(element, null, null, null);
            size++;
            return root;
        }

        TreeNode insertParentNode = null;
        TreeNode searchTempNode = root;

        while (searchTempNode != null && searchTempNode.val != null) {
            insertParentNode = searchTempNode;
            if (element < searchTempNode.val) {
                searchTempNode = searchTempNode.left;
            } else {
                searchTempNode = searchTempNode.right;
            }
        }

        TreeNode newNode = createNode(element, insertParentNode, null, null);
        if (insertParentNode.val > element) {
            insertParentNode.left = newNode;
        } else {
            insertParentNode.right = newNode;
        }

        size++;
        return newNode;
    }

    public TreeNode delete(int element) {
        TreeNode deleteNode = search(element);
        if (deleteNode != null) {
            return delete(deleteNode);
        } else {
            return null;
        }
    }

    private TreeNode delete(TreeNode deleteNode) {
        if (deleteNode == null) return null;

        TreeNode nodeToReturn = null;
        if (deleteNode.left == null) {
            nodeToReturn = transplant(deleteNode, deleteNode.right);
        } else if (deleteNode.right == null) {
            nodeToReturn = transplant(deleteNode, deleteNode.left);
        } else {
            TreeNode sucessorNode = getMinimum(deleteNode.right);
            if (sucessorNode.parent != deleteNode) {
                transplant(sucessorNode, sucessorNode.right);
                sucessorNode.right = deleteNode.right;
                sucessorNode.right.parent = sucessorNode;
            }
            transplant(deleteNode, sucessorNode);
            sucessorNode.left = deleteNode.left;
            sucessorNode.left.parent = sucessorNode;
            nodeToReturn = sucessorNode;
        }
        size--;
        return nodeToReturn;
    }


    /**
     * 将树中的一个节点（newNode）放置到另一个节点（nodeToReplace）的位置
     *
     * @param nodeToReplace
     * @param newNode
     * @return
     */
    private TreeNode transplant(TreeNode nodeToReplace, TreeNode newNode) {
        if (nodeToReplace.parent == null) {
            root = newNode;
        } else if (nodeToReplace == nodeToReplace.parent.left) {
            nodeToReplace.parent.left = newNode;
        } else {
            nodeToReplace.parent.right = newNode;
        }

        if (newNode != null) newNode.parent = nodeToReplace.parent;

        return newNode;
    }

    public boolean contains(int element) {
        return search(element) != null;
    }

    public int getMinimum() {
        return getMinimum(root).val;
    }

    public TreeNode getMinimum(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    public int getMaximum() {
        return getMaximum(root).val;
    }

    public TreeNode getMaximum(TreeNode node) {
        while (node.right != null) {
            node = node.right;
        }
        return node;
    }

    public int getSuccessor(int element) {
        return getSuccessor(search(element)).val;
    }

    private TreeNode getSuccessor(TreeNode node) {
        if (node.right != null) {
            return getMinimum(node.right);
        } else {
            TreeNode currentNode = node;
            TreeNode parentNode = node.parent;
            while (parentNode != null && currentNode == parentNode.right) {
                currentNode = parentNode;
                parentNode = parentNode.parent;
            }
            return parentNode;
        }
    }

    public int getSize() {
        return size;
    }

    /**
     * Tree traversal with printing element values. In order method.
     */
    public void printTreeInOrder() {
        printTreeInOrder(root);
    }

    /**
     * Tree traversal with printing element values. Pre order method.
     */
    public void printTreePreOrder() {
        printTreePreOrder(root);
    }

    /**
     * Tree traversal with printing element values. Post order method.
     */
    public void printTreePostOrder() {
        printTreePostOrder(root);
    }

    /*-------------------PRIVATE HELPER METHODS-------------------*/

    private void printTreeInOrder(TreeNode entry) {
        if (entry != null) {
            printTreeInOrder(entry.left);
            if (entry.val != null) {
                System.out.println(entry.val);
            }
            printTreeInOrder(entry.right);
        }
    }

    private void printTreePreOrder(TreeNode entry) {
        if (entry != null) {
            if (entry.val != null) {
                System.out.println(entry.val);
            }
            printTreeInOrder(entry.left);
            printTreeInOrder(entry.right);
        }
    }

    private void printTreePostOrder(TreeNode entry) {
        if (entry != null) {
            printTreeInOrder(entry.left);
            printTreeInOrder(entry.right);
            if (entry.val != null) {
                System.out.println(entry.val);
            }
        }
    }

    // -------------------------------- TREE PRINTING ------------------------------------
    public void printTree() {
        printSubtree(root);
    }

    public void printSubtree(TreeNode node) {
        if (node.right != null) {
            printTree(node.right, true, "");
        }
        printNodeValue(node);
        if (node.left != null) {
            printTree(node.left, false, "");
        }
    }

    private void printNodeValue(TreeNode node) {
        if (node.val == null) {
            System.out.print("<null>");
        } else {
            System.out.print(node.val.toString());
        }
        System.out.println();
    }

    private void printTree(TreeNode node, boolean isRight, String indent) {
        if (node.right != null) {
            printTree(node.right, true, indent + (isRight ? "        " : " |      "));
        }
        System.out.print(indent);
        if (isRight) {
            System.out.print(" /");
        } else {
            System.out.print(" \\");
        }
        System.out.print("----- ");
        printNodeValue(node);
        if (node.left != null) {
            printTree(node.left, false, indent + (isRight ? " |      " : "        "));
        }
    }

}